package com.maishi.programmer.tree;

/**
 * Created by brossdong on 2018/3/19.
 * 给定一棵二叉树和其中一个节点,如何找出中序遍历序列的下一个节点
 * 树中的节点除了有两个分别指向左,右的指针,还有一个指向父节点的指针
 */
public class TestTree2 {

    public TreeLinkNode getNext (TreeLinkNode pNode) {

        if (pNode == null) return null;
        TreeLinkNode tmp = null;
        //如果pNode的右子树为空
        if (pNode.right == null) {
            tmp = pNode;
            //如果该节点是某个最右节点
            while (tmp.next != null && tmp == tmp.next.right) {
                tmp = tmp.next;
                return tmp.next == null ? null : tmp.next;
            }
        }
        //如果右子树不为空，找到右子树中的最左节点
        tmp = pNode.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        return tmp;
    };


    private class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        
    }
}
